/*
 * Josh Lindoo
 * Login ID : lind6441
 * CS-102, Winter 2013
 * Programming Assignment 5
 * BinarySearchTree class: Basic Binary Search Tree
 * 					
 */

import java.util.*;

public class BinarySearchTree<T extends Comparable<T>> {
	
	protected TreeNode<T> root; //root node
	protected int numberOfItems; //track number of items
	
	//Default constructor
	public BinarySearchTree() {
		root = null; 
		numberOfItems = 0;
	}
	
	
	/*
	 * Method: search
	 * Purpose: Search db for matching object
	 * Parameters:
	 * 		T target:				target object
	 * 		TreeNode<T> currNode:	selected node
	 * Returns: boolean
	 */
	
	public boolean search(T target) {
		return search(target, root);
	}
	private boolean search(T target, TreeNode<T> currNode) {
		
		//if element doesn't exist
		if(currNode == null) return false;
		
		//if matching element found
		if(currNode.getDatum().equals(target)) return true;
		
		//if current element is < target, continue right, else go left
		if(currNode.getDatum().compareTo(target) < 0)
			return search(target, currNode.getRight());
		else
			return search(target, currNode.getLeft());
		
	}
	
	
	/*
	 * Method: add
	 * Purpose: Add object to the tree
	 * Parameters:
	 * 		T target: new object to add
	 * Returns: void
	 */
	
	public void add(T target) {
		
		TreeNode<T> current = root;
		TreeNode<T> previous = null;
		
		//fall into pos
		while(current != null) {
			previous = current;
			if(current.getDatum().compareTo(target) < 0)
				current = current.getRight();
			else
				current = current.getLeft();
		}
		
		//create new node with datum
		TreeNode<T> splice = new TreeNode<T>();
		splice.setDatum(target);
		
		//if no root node
		if(previous == null)
			root = splice;
		
		//else if new datum is bigger
		else if(previous.getDatum().compareTo(target) < 0)
			previous.setRight(splice);
		
		//else new datum is smaller or equal
		else
			previous.setLeft(splice);
		
		numberOfItems++;
		
	}
	
	
	/*
	 * Method: remove
	 * Purpose: recursive method to remove an object from the tree
	 * Parameters:
	 * 		T toRemove: object to remove
	 * 		TreeNode<T> currNode:	selected node
	 * Returns: void
	 */
	
	public void remove(T toRemove) {
		
		root = remove(toRemove, root);
		numberOfItems--;
		
	}
	private TreeNode<T> remove(T toRemove, TreeNode<T> currNode) {
		
		//if element doesn't exist in tree
		if(currNode == null)
			throw new NoSuchElementException();
		
		//if current element < toRemove, continue right
		if(currNode.getDatum().compareTo(toRemove) < 0) {
			currNode.setRight(remove(toRemove, currNode.getRight()));
			return currNode;
		}
		
		//if current element > toRemove, continue left
		if(currNode.getDatum().compareTo(toRemove) > 0) {
			currNode.setLeft(remove(toRemove, currNode.getLeft()));
			return currNode;
		}
		
		//if currNode's left link is null, return right side
		if(currNode.getLeft() == null) return currNode.getRight();
		
		//if currNode's right link is null, return left side
		if(currNode.getRight() == null) return currNode.getLeft();
		
		//hold onto the lower tree before removing currNode
		TreeNode<T> heir = currNode.getLeft();
		
		//find largest node
		while(heir.getRight() != null)
			heir = heir.getRight();
		
		//use largest node as replacement for removed node
		currNode.setDatum(heir.getDatum());
		
		//re-attach left side of tree
		currNode.setLeft(remove(heir.getDatum(), currNode.getLeft()));
		
		return currNode;
	}
	
	/*
	 * Method: removeAll
	 * Purpose: remove all movies
	 * Parameters: none
	 * Returns: void
	 */
	
	public void removeAll() {
		root = null;
	}
	
	/*
	 * Method: getNumberOfItems
	 * Purpose: Accessor for numberOfItems
	 * Parameters:	none
	 * Returns: int
	 */
	
	public int getNumberOfItems() {
		return numberOfItems;
	}
	
}
